package HASH_TABLE

func buildTree(preorder, inorder []int) *TreeNode {
	n := len(preorder)
	index := make(map[int]int, n)
	for i, x := range inorder {
		index[x] = i
	}

	var dfs func(int, int, int, int) *TreeNode
	dfs = func(preL, preR, inL, inR int) *TreeNode {
		if preL == preR { // 空节点
			return nil
		}
		leftSize := index[preorder[preL]] - inL // 左子树的大小
		left := dfs(preL+1, preL+1+leftSize, inL, inL+leftSize)
		right := dfs(preL+1+leftSize, preR, inL+1+leftSize, inR)
		return &TreeNode{preorder[preL], left, right}
	}
	return dfs(0, n, 0, n) // 左闭右开区间
}

//func buildTree(preorder []int, inorder []int) *TreeNode {
//	n := len(preorder)
//	index := make(map[int]int, n)
//	for i, x := range inorder {
//		index[x] = i
//	}
//	var dfs func(int, int, int, int) *TreeNode
//	dfs = func(preL, preR, inL, inR int) *TreeNode {
//		if preL == preR {
//			return nil
//		}
//		rootVal := preorder[preL]
//		rootInInorder := index[rootVal]
//
//		leftSize := rootInInorder - inL
//		left := dfs(preL+1, preL+1+leftSize, inL, inR)
//		right := dfs(preL+1+leftSize, preR, rootInInorder+1, inR)
//		return &TreeNode{
//			Val:   rootVal,
//			Left:  left,
//			Right: right,
//		}
//	}
//	return dfs(0, n, 0, n)
//
//}
// TreeNode 是二叉树节点的定义

// buildTree 根据前序遍历和中序遍历序列构建二叉树
// 参数 preorder：前序遍历序列（根-左-右）
// 参数 inorder：中序遍历序列（左-根-右）
// 返回值：构建出的二叉树的根节点

//func buildTree(preorder, inorder []int) *TreeNode {
//	n := len(preorder)
//	// 若序列为空，直接返回空树
//	if n == 0 {
//		return nil
//	}
//
//	// 创建中序遍历值到索引的映射表（哈希表）
//	// 作用：快速查找某个值在中序遍历中的位置（O(1)时间复杂度）
//	index := make(map[int]int, n)
//	for i, x := range inorder {
//		index[x] = i // key: 节点值，value: 该值在inorder中的索引
//	}
//
//	// 定义递归函数dfs，用于构建子树
//	// 参数说明（均为左闭右开区间，即[start, end)包含start到end-1的元素）：
//	// preL, preR：当前子树在前序遍历中的区间 [preL, preR)
//	// inL, inR：当前子树在中序遍历中的区间 [inL, inR)
//	var dfs func(int, int, int, int) *TreeNode
//	dfs = func(preL, preR, inL, inR int) *TreeNode {
//		// 终止条件：若前序区间为空（preL == preR），说明当前子树不存在，返回nil
//		if preL == preR {
//			return nil
//		}
//
//		// 1. 确定当前子树的根节点值
//		// 前序遍历的第一个元素（preL位置）就是当前子树的根节点
//		rootVal := preorder[preL]
//
//		// 2. 找到根节点在中序遍历中的位置
//		// 中序遍历中，根节点左边是左子树，右边是右子树
//		rootInInorder := index[rootVal]
//
//		// 3. 计算左子树的节点数量
//		// 中序遍历中，根节点左边的元素都属于左子树，数量为 rootInInorder - inL
//		leftSize := rootInInorder - inL
//
//		// 4. 递归构建左子树
//		// 左子树在前序中的区间：[preL+1, preL+1+leftSize)
//		// （根节点之后的leftSize个元素都是左子树的前序遍历）
//		// 左子树在中序中的区间：[inL, rootInInorder)
//		// （根节点左边的所有元素）
//		left := dfs(preL+1, preL+1+leftSize, inL, rootInInorder)
//
//		// 5. 递归构建右子树
//		// 右子树在前序中的区间：[preL+1+leftSize, preR)
//		// （左子树之后到结束的元素都是右子树的前序遍历）
//		// 右子树在中序中的区间：[rootInInorder+1, inR)
//		// （根节点右边的所有元素）
//		right := dfs(preL+1+leftSize, preR, rootInInorder+1, inR)
//
//		// 6. 创建当前根节点，连接左右子树并返回
//		return &TreeNode{
//			Val:   rootVal,
//			Left:  left,
//			Right: right,
//		}
//	}
//
//	// 初始调用：构建整棵树，前序区间[0, n)，中序区间[0, n)
//	return dfs(0, n, 0, n)
//}
